{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用说明与最佳实践\n",
    "\n",
    "- `std::list` 插入/删除任意位置为 O(1)，但随机访问为 O(n)；适用于需要频繁移动节点且保持迭代器稳定的场景。\n",
    "- `splice` 能在常数时间内在多个 `list` 间搬移节点（示例 2、5）。\n",
    "- 注意：`erase` 会使被删除节点的迭代器失效；其它迭代器保持有效。\n",
    "- 对性能敏感场景，可考虑 `std::list::size()` O(1)（C++11 起）与自定义分配器（例如 PMR）。\n",
    "- 构建/遍历仍有 cache miss 风险，若数据更偏向顺序访问，请评估 `std::deque` 或 `std::vector`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 序号 | 工程场景                                  | 文件名                         | 说明要点                                                     | 可运行示例代码       |\n",
    "| ---- | ----------------------------------------- | ------------------------------ | ------------------------------------------------------------ | -------------------- |\n",
    "| 1    | 高频插入/删除的事件队列（保持迭代器稳定） | `list_event_queue.cpp`         | `std::list` 中间擦除 O(1)，迭代器在非删除操作中保持有效，适合动态筛除任务 | 示例 1：事件队列     |\n",
    "| 2    | LRU 缓存（键到链表节点映射）              | `list_lru_cache.cpp`           | `list` + `unordered_map`，利用 `splice`/`push_front` 维护访问顺序 | 示例 2：LRU 缓存     |\n",
    "| 3    | 外部数据合并 / 流式排序                   | `list_merge_sort.cpp`          | 直接使用 `list::sort`、`list::merge`，避免大量搬移           | 示例 3：链表排序合并 |\n",
    "| 4    | 撤销 / 重做历史记录                       | `list_undo_redo.cpp`           | 光标指向当前状态，`splice`/迭代器移动支撑撤销重做到任意位置  | 示例 4：撤销重做     |\n",
    "| 5    | 多队列调度（就绪/等待队列切换）           | `list_splice_scheduler.cpp`    | `splice` O(1) 在不同列表之间转移节点，适合任务状态切换       | 示例 5：队列调度     |\n",
    "| 6    | 内存池 / 空闲链表管理                     | `list_free_list_allocator.cpp` | `std::list` 管理可变大小块，`remove_if`/`merge` 合并相邻空闲块，演示自定义分配策略 | 示例 6：空闲链表管   |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 示例 1：事件队列 (list_event_queue.cpp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 示例 2：LRU 缓存 (list_lru_cache.cpp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 示例 3：链表排序合并 (list_merge_sort.cpp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 示例 4：撤销重做 (list_undo_redo.cpp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 示例 5：队列调度 (list_splice_scheduler.cpp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 示例 6：空闲链表管理 (list_free_list_allocator.cpp)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
